Smallest sufficient team [Bit Manipulation]¶
Time: O(Mx2^N); Space: O(2^N); hard
In a project, you have a list of required skills req_skills, and a list of people. The i-th person people[i] contains a list of skills that person has.
Consider a sufficient team: a set of people such that for every required skill in req_skills, there is at least one person in the team who has that skill. We can represent these teams by the index of each person: for example, team = [0, 1, 3] represents the people with skills people[0], people[1], and people[3].
Return any sufficient team of the smallest possible size, represented by the index of each person.
You may return the answer in any order. It is guaranteed an answer exists.
Example 1:
Input: req_skills = [“java”,“nodejs”,“reactjs”], people = [[“java”],[“nodejs”],[“nodejs”,“reactjs”]]
Output: [0,2]
Example 2:
Input: req_skills = [“algorithms”,“math”,“java”,“reactjs”,“csharp”,“aws”], people = [[“algorithms”,“math”,“java”],[“algorithms”,“math”,“reactjs”],[“java”,“csharp”,“aws”],[“reactjs”,“csharp”],[“csharp”,“math”],[“aws”,“java”]]
Output: [1,2]
Constraints:
1 <= len(req_skills) <= 16
1 <= len(people) <= 60
1 <= len(people[i]), len(req_skills[i]), len(people[i][j]) <= 16
Elements of req_skills and people[i] are (respectively) distinct.
req_skills[i][j], people[i][j][k] are lowercase English letters.
Every skill in people[i] is a skill in req_skills.
It is guaranteed a sufficient team exists.
Hints:
Do a bitmask DP.
For each person, for each set of skills, we can update our understanding of a minimum set of people needed to perform this set of skills.
1. Dynamic programming [O(Mx2^N), O(2^N)]¶
Algorithm
Use bit representation of all possible tasks, eg. Input: req_skills = [“java”,“nodejs”,“reactjs”]:
000 task0 ()
100 task1 (Java)
010 task2 (Nodejs)
110 task3 (Java, Nodejs)
…
111 taskn (Java, nodejs, reactjs)
The last task (or task we want) is one with all the skills.
How many tasks do we have?
111 = 2^3 - 1
Use bitwise to represent a person’s skills set.
For Example:
people = [[“java”],[“nodejs”],[“nodejs”,“reactjs”]]
person0 [“java”] => 100
person2 [“nodejs”, “rectjs”] => 011
Use a dp (matrix or dic) to cache the states.
dp[person_i][task_j] = the smallest team to complete task_j up to person_i.
Use person_i’s skill, do a bitwise or opration with every task_j => gets a new_task_k,
That means with person_i’s skills, we can complete a new task_k. We do that for every person, for every task.
person Task new_task 100 | 011 => 111 010 | 011 => 011
How do we update dp?
base case:
For task 0 (or 000 in example above), it’s []. b/c we don’t need anyone to complete that.
general case:
if with the addition person_i, (with existing task_j, after bitwise or), we can complete task_k, then compare the length of current team with the new team.
[39]:
class Solution1(object):
"""
Time: O(M*(2^N)), M = num of people, N = num of required_skills
Space: O(2^N)
"""
def smallestSufficientTeam(self, required_skills, people_skills):
"""
:type required_skills: List[str]
:type people_skills: List[List[str]]
:rtype: List[int]
"""
dp = {0: []}
# map {skill_str_name : index_in_bit}
skill_to_index_map = {
skill: index for index, skill in enumerate(required_skills)
}
for index in range(len(people_skills)):
person_skills_bit_rep = 0
for skill in people_skills[index]:
person_skills_bit_rep |= (1 << skill_to_index_map[skill])
tasks = list(dp.keys())
for task_i in tasks:
new_task = (task_i | person_skills_bit_rep)
if (new_task not in dp) or (len(dp[new_task]) > len(dp[task_i]) + 1):
dp[new_task] = dp[task_i] + [index]
return dp[(1 << len(required_skills)) - 1]
[40]:
s = Solution1()
req_skills = ["java","nodejs","reactjs"]
people = [
["java"],
["nodejs"],
["nodejs","reactjs"]
]
assert s.smallestSufficientTeam(req_skills, people) == [0,2]
req_skills = ["algorithms","math","java","reactjs","csharp","aws"]
people = [
["algorithms","math","java"],
["algorithms","math","reactjs"],
["java","csharp","aws"],
["reactjs","csharp"],
["csharp","math"],
["aws","java"]
]
assert s.smallestSufficientTeam(req_skills, people) == [1,2]